package algo.graph;

import ds.adt.Digraph;
import ds.adt.Queue;
import ds.adt.Stack;

public class BreadthFirstSearchDirectedPaths {
	private boolean[] marked;
	private int[] edgeTo;
	private int s;

	public BreadthFirstSearchDirectedPaths(Digraph g, int s) {
		this.marked = new boolean[g.V()];
		this.edgeTo = new int[g.V()];
		this.s = s;

		bfs(g, s);
	}

	private void bfs(Digraph g, int v) {
		Queue<Integer> queue = new Queue<Integer>();
		marked[v] = true;
		queue.enqueue(v);

		while (!queue.isEmpty()) {
			v = queue.dequeue();
			for (int w : g.adj(v)) {
				if (!marked[w]) {
					marked[w] = true;
					edgeTo[w] = v;
					queue.enqueue(w);
				}
			}
		}
	}

	public boolean hasPathTo(int v) {
		return marked[v];
	}

	public Iterable<Integer> pathTo(int v) {
		Stack<Integer> path = new Stack<Integer>();
		if (!hasPathTo(v)) {
			return path;
		}
		for (int w = v; w != s; w = edgeTo[w]) {
			path.push(w);
		}
		path.push(s);

		return path;
	}

	public static void main(String[] args) {

		Digraph g = new Digraph(6);
		g.addEdge(0, 1);
		g.addEdge(1, 2);
		g.addEdge(2, 5);
		g.addEdge(0, 5);
		g.addEdge(0, 3);
		g.addEdge(0, 4);

		BreadthFirstSearchDirectedPaths path = new BreadthFirstSearchDirectedPaths(g, 0);
		System.out.print("BFS (Shortest) PATH : ");

		for (Integer i : path.pathTo(5)) {
			System.out.print(i + " ");
		}
	}
}
